拉蒙碎碎念

還記得以前剛學程式設計的時候，老師都會從幾個較簡單的演算法教起，讓學生比較好學也快上手。其實演算法就是在學邏輯，語法啊、技巧啊，我個人倒覺得是其次。因此之後的文章都會著重在邏輯的概念，語法和效率上或許可以更好，但我偏不改，至少簡單明瞭。(笑)

桶子排序法 (Bucket Sort) 想法很簡單，其實就是準備幾個桶子，將要排序的資料分類丟至指定的桶子中，再依序將桶子裡的東西取出。有點類似資源回收的概念啦～

假設我們現在有一筆將班上的成績想要排序：

data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

並由小到大排序成：

data = [23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]

1. 準備桶子

首先要來準備桶子，因為成績最高為 100 分，很簡單的做法就是準備 101 個桶子(因有有人可能 0 分)。

max_score = 100
bucket = []
for i in range(max_score+1):
    bucket.append(0)

還沒丟東西，所以桶子裡面都是空的，值都為 0。

2. 丟垃圾 分類成績

將成績一一讀取，並丟到相對應的桶子，有幾個就加幾個。

for score in data:
    bucket[score] = bucket[score] + 1

3. 回收垃圾 讀取成績

先設一個游標，第二行是依序讀取桶子裡的資料，當桶子的資料不為 0 的時候，表示我們有在裡面存放成績。最後三行代表每個桶子都有編號，我們將編號存回 data 裡面，看有幾個就存幾個。

index = 0
for i in range(len(bucket)):
    if bucket[i] != 0:
        for j in range(bucket[i]):
            data[index] = i
            index += 1

就這樣，默默的把垃圾成績分類再撿出來還依序排好，覺得真的是櫻櫻美代子哈哈。

其實Python就有內建的函式sort()和resorted()可以做陣列的排序。
但問題是當資料量大的時候，內建的函式不一定會比較快，所以數學家才會發明一堆演算法，就是為了要讓工作更快、更快、再更快。

除了讓事情更有效率，也學到了邏輯呢!

全部的程式碼

程式時間複雜度：O(M+N)

data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def bucketsort(data):
    max_score = 100
    bucket = []
    
    for i in range(max_score+1):
        bucket.append(0)
    for score in data:
        bucket[score] = bucket[score] + 1

    index = 0
    for i in range(len(bucket)):
        if bucket[i] != 0:
            for j in range(bucket[i]):
                data[index] = i
                index += 1

bucketsort(data)
print(data)

花式自虐 進階練習

再如果假設我們的資料還包含了姓名在內，那要如何排序呢？

data = [['Abby', 58], ['Julia', 44], ['Jane', 31], ['Stephen', 76], ['Ryn', 82], ['Justin', 99], ['Caroline', 65], ['James', 87], ['Damon', 25], ['Elena', 76]]

其實原理都差不多，只是我將桶子數量變少，並且將桶子裡的姓名也依照字母排序，其中用的就是內建的函式resorted()。

完整程式碼：

data = [['Abby', 58], ['Julia', 44], ['Jane', 31], ['Stephen', 76], ['Ryn', 82], ['Justin', 99], ['Caroline', 65], ['James', 87], ['Damon', 25], ['Elena', 76]]

def bucketsort_hash(data):
    max_score = 100
    bucket = []
    bucket_num = lambda x: int(x/33)
    
    for i in range(bucket_num(max_score)+1):
        bucket.append([])

    for x in data:
        index = bucket_num(x[1])
        bucket[index].append(x)

    for i, flag in enumerate(bucket):
        if flag != [] :
            bucket[i] = sorted(bucket[i], key=lambda x: x[1])

    index = 0
    for i in bucket:
        if i != []:
            for j in i:
                data[index] = j
                index += 1

bucketsort_hash(data)
print(data)

以上的範例是用陣列來結合名字和成績，但其實也可以用字典來做運算，就留待讀者去思考了。